using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0297. 二叉树的序列化与反序列化")]
    public class No0297_BinaryTreeSerializeCodec : AbsBaseTestItem
    {
        /// <summary>
        /// Definition for a binary tree node.
        /// </summary>
        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            Func<TreeNode, TreeNode, bool> equalsMethod = (n1, n2) => n1.ToJSONString() == n2.ToJSONString();

            TreeNode root = new TreeNode(1)
            {
                left = new TreeNode(2),
                right = new TreeNode(3)
                {
                    left = new TreeNode(4),
                    right = new TreeNode(5)
                    {
                        right = new TreeNode(6),
                    },
                },
            };

            Codec codec = new Codec();
            Assert.TestExe(codec.serialize, root, "a1,n2,a3,n4,r5,n6");
            Assert.TestExe(codec.deserialize, "a1,n2,a3,n4,r5,n6", root);
            Assert.TestExe(n => codec.deserialize(codec.serialize(n)), root, equalsMethod, root);

            Codec2 codec2 = new Codec2();
            Assert.TestExe(n => codec.deserialize(codec.serialize(n)), root, equalsMethod, root);
        }

        public class Codec
        {
            /// <summary>
            /// Encodes a tree to a single string.
            /// </summary>
            public string serialize(TreeNode root)
            {
                List<string> strs = new List<string>();
                if (root != null)
                {
                    if (root.left != null && root.right != null)
                    {
                        strs.Add("a" + root.val);
                        strs.Add(serialize(root.left));
                        strs.Add(serialize(root.right));
                    }
                    else if (root.left != null)
                    {
                        strs.Add("l" + root.val);
                        strs.Add(serialize(root.left));
                    }
                    else if (root.right != null)
                    {
                        strs.Add("r" + root.val);
                        strs.Add(serialize(root.right));
                    }
                    else
                    {
                        strs.Add("n" + root.val);
                    }
                }
                return string.Join(",", strs.ToArray());
            }

            /// <summary>
            /// Decodes your encoded data to tree.
            /// </summary>
            public TreeNode deserialize(string data)
            {
                if (string.IsNullOrEmpty(data))
                {
                    return null;
                }
                string[] strs = data.Split(",");
                int startIndex = 0;
                var root = ToNode(strs[startIndex], out char sign);
                startIndex = deserialize_array(strs, root, startIndex, sign);
                return root;
            }

            private TreeNode ToNode(string item, out char sign)
            {
                sign = item[0];
                item = item.Substring(1, item.Length - 1);
                return new TreeNode(int.Parse(item));
            }

            private int deserialize_array(string[] strs, TreeNode tree, int startIndex, char sign)
            {
                if (sign == 'a')
                {
                    startIndex++;
                    tree.left = ToNode(strs[startIndex], out sign);
                    startIndex = deserialize_array(strs, tree.left, startIndex, sign);

                    startIndex++;
                    tree.right = ToNode(strs[startIndex], out sign);
                    startIndex = deserialize_array(strs, tree.right, startIndex, sign);
                    return startIndex;
                }
                else if (sign == 'l')
                {
                    startIndex++;
                    tree.left = ToNode(strs[startIndex], out sign);
                    startIndex = deserialize_array(strs, tree.left, startIndex, sign);
                    return startIndex;
                }
                else if (sign == 'r')
                {
                    startIndex++;
                    tree.right = ToNode(strs[startIndex], out sign);
                    startIndex = deserialize_array(strs, tree.right, startIndex, sign);
                    return startIndex;
                }
                return startIndex;
            }
        }

        /// <summary>
        /// 不是自己写的, 来源答案中: 执行用时为 152 ms 的范例 大佬代码!!!
        /// </summary>
        public class Codec2
        {
            // Encodes a tree to a single string.
            public string serialize(TreeNode root)
            {
                var sb = new StringBuilder();
                BuildString(root, sb);
                return sb.ToString();
            }
            private void BuildString(TreeNode root, StringBuilder sb)
            {
                if (root == null)
                {
                    sb.Append("null").Append(",");
                    return;
                }
                sb.Append(root.val).Append(",");
                BuildString(root.left, sb);
                BuildString(root.right, sb);
            }

            // Decodes your encoded data to tree.
            public TreeNode deserialize(string data)
            {
                var nodes = data.Split(",");
                var queue = new Queue<string>();
                foreach (var node in nodes)
                {
                    queue.Enqueue(node);
                }
                return BuildTree(queue);
            }
            private TreeNode BuildTree(Queue<string> queue)
            {
                var node = queue.Dequeue();
                if (node.Equals("null"))
                    return null;
                var newNode = new TreeNode(int.Parse(node));
                newNode.left = BuildTree(queue);
                newNode.right = BuildTree(queue);
                return newNode;
            }
        }
    }
}
